我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode-cn.com/problems/reverse-words-in-a-string/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public:
    string reverseWords(string s)
    {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;
        for (int start = 0; start < n; start++)
        {
            if (s[start] != ' ') //从开头向后遍历直到遇到不是空格的地方
            {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0)
                    s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;
                while (end < n && s[end] != ' ')
                    s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

思路

首先我想表达我对js和python的怀念…手写api太痛苦了
好难啊，为什么Med就这么难

上手

  1. 定义start = 0，从头开始遍历数组
  2. 首先我们可以看到一个if (s[start] != ‘ ‘)，它的作用是让数组遍历到第一个不是空格的地方再往下执行
  3. 然后我们又能看到一个if (idx != 0)，这又是什么意思呢？如果不是第一个单词（开头不需要空格），则先补一个空格（分隔开每个单词）
  4. 下面的步骤总结一下就是先抽取出单个单词，放入上一个单词空一个空格开始的位置，然后对这个单词进行反转
  5. 最后我们把数组末尾多出来的部分erase掉

对于刚上手的小白还是有一些难度的，建议没事就拿出来默一默
有哪些思想呢？比如分割？单独处理？O(1)的额外空间？